﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace MMDemo
{
    /*
   *	枚举当前可执行类型
   */
    public enum OperateTypeSearch
    {
        Seqsch,
        Halfsch,
        Insertsch,
        Fibonacci,
    }
    class AnimationSearch:InterfaceDataStructs
    {
        /// <summary>
        /// 类成员
        /// </summary>
        private Form Animation_Form = null;//演示窗体，用于构造函数的初始化
        private int Animation_width = 0;//演示窗体的宽度
        private int Animation_height = 0;//演示窗体的高度

        public Bitmap BufferBmp = null;//双缓冲画布
        private Graphics BufferGrap = null;//画笔
        private DrawHandler RefreshHandler = null;

        private int[] SaveSearchData;//保存查找数据
        private int SaveKeyData;//要查找的数据
        private int SearchDataNum = 0;
        private int CurLocate = -1;
        private int LowLocate = -1;
        private int HighLocate = 100;
        private const int ElementWidth = 60;
        String path = Application.StartupPath;
        private Bitmap[] ImageData = new Bitmap[5];

        public AnimationSearch(Form An_Form, DrawHandler refreshHandler, int An_Width, int An_Height)
        {
            this.Animation_Form = An_Form;
            this.RefreshHandler = refreshHandler;
            this.Animation_width = An_Width;
            this.Animation_height = An_Height;
            //设置画布和画笔
            BufferBmp = new Bitmap(this.Animation_width, this.Animation_height);
            BufferGrap = Graphics.FromImage(BufferBmp);
            string[] name = {"search_0.png","search_1.png","search_2.png","search_3.png","search_4.png"};
            for (int i = 0; i < 5;++i )
            {
                ImageData[i] = (Bitmap)Image.FromFile(path + "/image/"+name[i]);
            }
        }

        //重写初始化数据方法
        public void InitData()
        {
            ResetBuffer(Animation_width, Animation_height);
            switch (GlobalSearch.operateType)
            {
                case OperateTypeSearch.Seqsch:
                default:
                    ResetData(GlobalSearch.SearchData,GlobalSearch.KeyData); break;
            }
            DrawElement();
        }

        /// <summary>
        /// 刷新
        /// </summary>
        /// <returns></returns>
        private bool Refresh()
        {
            try
            {
                if (Animation_Form.IsHandleCreated)
                    Animation_Form.Invoke(RefreshHandler);
            }
            catch (Exception ex)
            {
                MessageBox.Show(Animation_Form,ex.Message);
                return false;
            }
            return true;
        }

        /// <summary>
        /// 恢复方法中调用数据初始化方法
        /// </summary>
        public void ResetData()
        {
            InitData();
        }

        /// <summary>
        /// 数据重置方法，重载
        /// </summary>
        /// <param name="data"></param>
        /// <param name="key"></param>
public void ResetData(int[] data,int key)
{
    SaveSearchData = data;
    SaveKeyData = key;
    SearchDataNum = data.Length;

    CurLocate = -1;
    LowLocate = -1;
    HighLocate = 100;
}
        public Bitmap GetBufferBmp()
        {
            return BufferBmp;
        }
        //重新设置双缓冲画布和Graphics
        public void ResetBuffer(int Width, int Height)
        {
            this.Animation_width = Width;
            this.Animation_height = Height;
            if (null != BufferBmp)
            {
                BufferBmp.Dispose();
                BufferBmp = null;
            }
            if (null != BufferGrap)
            {
                BufferGrap.Dispose();
                BufferGrap = null;
            }

            BufferBmp = new Bitmap(this.Animation_width, this.Animation_height);
            BufferGrap = Graphics.FromImage(BufferBmp);
            DrawElement();
        }

        private int stop_flag = -1;
        public void Animation()
        {
            switch (GlobalSearch.operateType)
            {
                case OperateTypeSearch.Seqsch:
                    stop_flag = Search_Seqsch(SaveSearchData,SaveKeyData);
                    break;
                case OperateTypeSearch.Halfsch:
                    stop_flag = Search_Halfsch(SaveSearchData, SaveKeyData);
                    break;
                case OperateTypeSearch.Insertsch:
                    stop_flag = Search_Insertsch(SaveSearchData, SaveKeyData);
                    break;
                case OperateTypeSearch.Fibonacci:
                    stop_flag = Search_Fibonacci(SaveSearchData, SaveKeyData);
                    break;
            }
            if (stop_flag!=-1)
            {
                MessageBox.Show(Animation_Form,"查找成功，位置为" + stop_flag.ToString());
            }
            else
            {
                MessageBox.Show(Animation_Form, "查找结束，未找到匹配项!");
            }
            MessageBox.Show(Animation_Form, "算法演示结束!");
             SysMainForm.AnimationForm.ChangeExcuteOverBtnsEnable();
            
        }
        public int Search_Seqsch(int[] data,int key)
        {
            SetExcuteLine(1);
            SetExcuteLine(2);
            int i = -1;
            SetExcuteLine(3);
            for ( i = 0; i < data.Length; i++)
            {
                SetExcuteLine(4);
                CurLocate = i;
                FlickerCompareElement();
                if (data[i] == key)
                {
                    SetExcuteLine(5);
                    FlickerOkElement();
                    break;
                }
                SetExcuteLine(6);
                SetExcuteLine(3);
            }
            SetExcuteLine(7);
            if (i < data.Length)
            {//查找成功返回下标，否则返回-1
                SetExcuteLine(8);
                return i+1;
            }
            else
            {
                SetExcuteLine(9);
                SetExcuteLine(10);
                return -1;
            }
        }

        public int Search_Halfsch(int[] data,int key)
        {
            SetExcuteLine(1);
            SetExcuteLine(2);
            LowLocate = 0;
            HighLocate = data.Length-1;            
            int mid = 0;
            SetExcuteLine(3);
             Array.Sort(data);
             Thread.Sleep(_Speed);
             DrawElement();
             SetExcuteLine(4);
             int tempAB = -1;
             CurLocate = LowLocate;
             FlickerCompareElement();
             tempAB = CompareAB(key, data[LowLocate]);
             if (tempAB != 1)
             {
                 if (tempAB == 0)
                 {
                     SetExcuteLine(6);
                     FlickerOkElement();
                     SetExcuteLine(7);
                     return 1;
                 }
                 else
                 {
                     SetExcuteLine(5);
                     return -1;
                 }
             }
             CurLocate = HighLocate;
             SetExcuteLine(8);
             FlickerCompareElement();
             tempAB = CompareAB(key, data[HighLocate]);
             if (tempAB != -1)
             {
                 if (tempAB == 0)
                 {
                     SetExcuteLine(10);
                     FlickerOkElement();
                     SetExcuteLine(11);
                     return HighLocate + 1;
                 }
                 else
                 {
                     SetExcuteLine(9);
                     return -1;
                 }
             }
             SetExcuteLine(12);
             while (LowLocate <= HighLocate)
             {
                 SetExcuteLine(13);
                 mid = (LowLocate + HighLocate) / 2;
                 CurLocate = mid;
                 SetExcuteLine(14);
                 FlickerCompareElement();
                if(data[mid]==key)
                {
                    SetExcuteLine(15);
                    FlickerOkElement();
                    return mid+1;
                }
                SetExcuteLine(17);
                if (data[mid]<key)
                {
                    SetExcuteLine(18);
                    LowLocate = mid + 1;
                    Thread.Sleep(_Speed);
                    DrawElement();
                }
                else
                {
                    SetExcuteLine(20);
                    SetExcuteLine(21);
                    HighLocate = mid - 1;
                    Thread.Sleep(_Speed);
                    DrawElement();
                }
                SetExcuteLine(12);
             }
             SetExcuteLine(24);
             return -1;
        }

        public int Search_Insertsch(int[] data, int key)
        {
            SetExcuteLine(1);
            SetExcuteLine(2);
            LowLocate = 0;
            HighLocate = data.Length-1;
            int mid = 0;
            SetExcuteLine(3);
            Array.Sort(data);
            Thread.Sleep(_Speed);
            DrawElement();
            int tempAB = -1;
            SetExcuteLine(4);
            CurLocate = LowLocate;
            FlickerCompareElement();
            tempAB = CompareAB(key, data[LowLocate]);
            if (tempAB != 1)
            {
                if (tempAB == 0)
                {
                    SetExcuteLine(6);
                    FlickerOkElement();
                    SetExcuteLine(7);
                    return 1;
                }
                    
                else
                {
                    SetExcuteLine(5);
                    return -1;
                }
            }
            CurLocate = HighLocate;
            SetExcuteLine(8);
            FlickerCompareElement();
            tempAB = CompareAB(key, data[HighLocate]);
            if (tempAB != -1)
            {
                if (tempAB == 0)
                {
                    SetExcuteLine(10);
                    FlickerOkElement();
                    SetExcuteLine(11);
                    return HighLocate + 1;
                }
                else
                {
                    SetExcuteLine(9);
                    return -1;
                }
            }
            SetExcuteLine(12);
            while (LowLocate <= HighLocate)
            {
                SetExcuteLine(13);
                if (key < data[LowLocate] || key > data[HighLocate])
                {
                    SetExcuteLine(14);
                    break;
                }
                SetExcuteLine(15);
                mid =LowLocate+(int)( (key - data[LowLocate])*1.0/(data[HighLocate]-data[LowLocate])*(HighLocate-LowLocate));
                CurLocate = mid;
                SetExcuteLine(16);
                FlickerCompareElement();
                if (data[mid] == key)
                {
                    SetExcuteLine(17);
                    FlickerOkElement();
                    return mid + 1;
                }
                SetExcuteLine(18);
                if (data[mid] < key)
                {
                    SetExcuteLine(19);
                    LowLocate = mid + 1;
                    Thread.Sleep(_Speed);
                    DrawElement();
                }
                else
                {
                    SetExcuteLine(20);
                    SetExcuteLine(21);
                    HighLocate = mid - 1;
                    Thread.Sleep(_Speed);
                    DrawElement();
                }
                SetExcuteLine(12);
            }
            SetExcuteLine(24);
            return -1;
        }


        public int Search_Fibonacci(int[] data, int key)
        {
            SetExcuteLine(1);
            SetExcuteLine(2);
            SetExcuteLine(3);
            Array.Sort(data);
            LowLocate = 0;
            HighLocate = data.Length - 1;
            Thread.Sleep(_Speed);
            DrawElement();
            SetExcuteLine(4);
            int tempAB = -1;
            CurLocate = LowLocate;
            FlickerCompareElement();
            tempAB = CompareAB(key, data[LowLocate]);
            if (tempAB!=1)
            {
                if (tempAB == 0)
                {
                    SetExcuteLine(6);
                    FlickerOkElement();
                    SetExcuteLine(7);
                    return 1;
                }

                else
                {
                    SetExcuteLine(5);
                    return -1;
                }
            }
            
            CurLocate = HighLocate;
            SetExcuteLine(8);
            FlickerCompareElement();
            tempAB = CompareAB(key, data[HighLocate]);
            if (tempAB!=-1)
            {
                if (tempAB == 0)
                {
                    SetExcuteLine(10);
                    FlickerOkElement();
                    SetExcuteLine(11);
                    return HighLocate + 1;
                }
                else
                {
                    SetExcuteLine(9);
                    return -1;
                }
            }
            
            int[] fib = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
            SetExcuteLine(12);
            int index, fR, fL, temp;
            int mid = -1;
            SetExcuteLine(13);
            for (index = 0; fib[index] < data.Length + 1; index++);//获得初始量            
            SetExcuteLine(14);
            mid = data.Length - fib[index - 2] + 1;
            SetExcuteLine(15);
            fR = fib[index - 2];//右偏移量
            SetExcuteLine(16);
            fL = fib[index - 3];//左偏移量
            SetExcuteLine(17);
            while (mid>=0)
            {
                SetExcuteLine(18);
                CurLocate = mid-1;
                FlickerCompareElement();
                if (key == data[mid-1])
                {
                    FlickerOkElement();
                    SetExcuteLine(19);
                    return mid;
                }
                SetExcuteLine(21);
                CurLocate = mid - 1;
                FlickerCompareElement();
                if (key < data[mid-1])
                {
                    SetExcuteLine(22);
                    if (fL == 0) break;
                    SetExcuteLine(23);
                    SetExcuteLine(24);
                    HighLocate = mid-2;
                    Thread.Sleep(_Speed);
                    DrawElement();
                    SetExcuteLine(25);
                    mid -= fL;//mid减去左偏移量
                    CurLocate = mid-1;
                    Thread.Sleep(_Speed);
                    DrawElement();
                    temp = fR;
                    fR = fL;
                    fL = temp - fL;//更改左偏移量
                    
                }
                SetExcuteLine(28);
                CurLocate = mid - 1;
                FlickerCompareElement();
                if (key > data[mid-1])
                {
                    SetExcuteLine(29);
                    if (fR == 1) break;
                    SetExcuteLine(30);
                    SetExcuteLine(31);
                    LowLocate = mid;
                    Thread.Sleep(_Speed);
                    DrawElement();
                    SetExcuteLine(32);
                    mid = mid + fL;//mid加上左
                    Thread.Sleep(_Speed);
                    DrawElement();
                    fR -= fL;
                    fL -= fR;
                }
                SetExcuteLine(17);
            }
            SetExcuteLine(37);
            return -1;
        }

        public int CompareAB(int A,int B)
        {
            if (A==B)
            {
                return 0;
            }
            else if(A<B)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }

        public bool IsCompare = false;
        public bool IsOk = false;
        private void FlickerCompareElement()
        {
            for (int i = 1; i <= 6; ++i)
            {
                Thread.Sleep(_Speed/3);
                if (i % 2 != 0)
                {
                    IsCompare = true;
                    IsOk = false;
                }
                else
                {
                    IsCompare = false;
                    IsOk = false;
                }
                DrawElement();
            }
        }

        private void FlickerOkElement()
        {
            for (int i = 1; i <= 6; ++i)
            {
                Thread.Sleep(_Speed/3);
                if (i % 2 != 0)
                {
                    IsCompare = false;
                    IsOk = true;
                }
                else
                {
                    IsCompare = false;
                    IsOk = false;
                }
                DrawElement();
            }
        }

        private int index = 1;
        private Brush bs = Brushes.Blue;
        public void DrawElement()
        {
            BufferGrap.DrawImage(PublicDataClass.DemoPicture, 0, 0, Animation_width, Animation_height);
            if (SaveSearchData==null)
            {
                return;
            }
            int x = 0;
            int y = Animation_height / 2 - ElementWidth / 2;
            for (int i = 0; i < SaveSearchData.Length;++i )
            {
                index = 1;
                bs = Brushes.Blue;
                x = (Animation_width - SaveSearchData.Length * ElementWidth) / 2 + i * ElementWidth;                
                if ((i < CurLocate&&GlobalSearch.operateType==OperateTypeSearch.Seqsch) || i < LowLocate || i > HighLocate)
                {
                    bs = Brushes.Gray;
                    index = 2;
                } 
                if (LowLocate == i&&GlobalSearch.operateType!= OperateTypeSearch.Fibonacci)
                {
                    index = 3;
                    BufferGrap.DrawString("low", new Font("微软雅黑", 18), Brushes.Yellow, x + ElementWidth / 5, y + ElementWidth / 5 + ElementWidth);
                }
                else if (HighLocate == i && HighLocate > LowLocate&&GlobalSearch.operateType != OperateTypeSearch.Fibonacci)
                {
                    index = 4;
                    BufferGrap.DrawString("high", new Font("微软雅黑", 18), Brushes.Yellow, x + ElementWidth / 5, y + ElementWidth / 5 + ElementWidth);
                }
                if (IsCompare && CurLocate == i)
                {
                    bs = Brushes.Red;
                    index = 4;
                }
                if (IsOk && CurLocate == i)
                {
                    bs = Brushes.Yellow;
                    index = 0;
                }
               
                if(CurLocate == i)
                {
                    BufferGrap.DrawImage(ImageData[index], x, y - ElementWidth, ElementWidth, ElementWidth);
                    BufferGrap.DrawString(SaveKeyData.ToString(), new Font("微软雅黑", 18), bs, x + ElementWidth / 5, y + ElementWidth / 5 - ElementWidth);
                }
                BufferGrap.DrawImage(ImageData[index], x, y, ElementWidth, ElementWidth);
                BufferGrap.DrawString(SaveSearchData[i].ToString(), new Font("微软雅黑", 18), bs, x + ElementWidth / 5, y + ElementWidth / 5);
            }
            Refresh();
        }

        private const int SPEED = 1000;
        private int _Speed = SPEED;
        public void SetSpeed(float scale)
        {
            _Speed = (int)(SPEED * scale);
        }

        private void SetExcuteLine(int line)
        {
            if (line != GlobalBinTree.cur_line)
            {
                GlobalSort.cur_line = line;
                Thread.Sleep((int)(1000 * PublicDataClass.scale));
                SysMainForm.AnimationForm.SetSelectLine(line);
            }
        }
    }
}
